『Copy-and-Patch Compilation: A fast compilation algorithm for high-level languages and bytecode』
1. どんなもの？
WebAssemblyへの高速コンパイル & パフォーマンスが良いコードを生成できることが示されている
2. 先行研究と比べてどこがすごい？
Copy-and-Patchで作られたWebAssemblyコンパイラは、Liftoffコンパイラより4.9倍から6.5倍高速にコードを生成できる 3. 技術や手法のキモはどこ？
事前に作成されたバイナリコードのスニペット（stencil）を用意し、それをコピー＆パッチすることでコード生成を行う。スニペット群はStencilライブラリ。 継続渡しスタイル(Continuation-Passing Style; CPS)：スタックフレームを最適化し、レジスタ割り当てを工夫することで効率的なコード生成を可能にする。 スーパーノード（Supernode）：ASTノード単位ではなく、一般的なコードパターンをまとめたstencilを用いることで、最適化を強化。
MetaVar：C++テンプレートメタプログラミングを利用して、様々なバリエーションのstencilを自動生成し、LLVMを活用してコンパイル。
4. どうやって有効だと検証した？
WebAssemblyコンパイラはPolyBenchベンチマークによる「起動までの時間」と、「起動から実行までの時間」を散布図で比較 SQLデータベースクエリーコンパイラは、TPC-HによるDBベンチマークで検証 Fig. 6. Copy-and-Patch can be used by metaprogramming systems to speed up their interpreters past LLVM -O0. And it can be combined with LLVM to let the user request higher optimization levels when the increased performance can amortize the orders of magnitude higher compilation cost.
パレート最適性による分析：コンパイル時間と実行速度のトレードオフを評価し、Copy-and-Patchが従来のベースラインコンパイラを凌駕することを確認。
5. 議論はある？
6. 次に読むべき論文は？
Abstructの訳
code:memo
高速なコンパイルは、最新のデータベースシステムのクエリコンパイラや、最新のブラウザのWebAssembly仮想マシンのように、実行時にコンパイルが行われる場合に重要である。我々は、非常に高速なコンパイル技術であり、かつ良質なコードを生成するコピー＆パッチを紹介する。コピー＆パッチは、バイナリ実装の大規模なライブラリからコードをつなぎ合わせることで、高レベル言語と低レベルバイトコードプログラムの両方をバイナリコードに変換することが可能です。これらのバイナリ実装は、コード生成時に欠損値を挿入しなければならない穴があるため、ステンシルと呼んでいます。ステンシルライブラリの構築方法を示し、最適化されたバイナリコードを生成するコピーアンドパッチアルゴリズムを説明する。
コピー＆パッチの使用例として、メタプログラミングを目的とした高レベルC言語用コンパイラとWebAssembly用コンパイラの2つを示す。このコンパイラは、ASTを構築するのにかかる時間よりも短い時間でASTからコードを生成することができ、コンパイルコストを無視できる。このメタプログラミングの上にSQLデータベースクエリーコンパイラを実装し、TPC-Hデータベースベンチマークにおいて、コピーアンドパッチはLLVM -O0よりも2桁、より高い最適化レベルよりも3桁高速にコードを生成することを示しました。また、生成されたコードは、解釈よりも1桁、LLVM -O0よりも14%高速に実行されます。WebAssemblyコンパイラは、Google ChromeのWebAssemblyベースラインコンパイラであるLiftoffよりも4.9倍から6.5倍高速にコードを生成します。また、CoremarkとPolyBenchCのWebAssemblyベンチマークでは、生成されたコードはLiftoffのものを39%〜63%上回っています。
Google ChromeのWebAssemblyベースラインコンパイラ
ベースラインコンパイラとは...?
CPUのベンチマーク
Transaction Processing Performance Council (TPC) によって定義されたデータベースのベンチマーク
多分著者の動画
Copy-and-Patch Compilation - YouTube
https://www.youtube.com/watch?v=PaQJcBdwG9Y
table:訳
Copy-and-Patch Compilation コピー・アンド・パッチコンパイル
startup delay 起動する
negligible 無視できる
empirically 経験的に
state-of-the-art 最先端の
domain-specific ドメイン固有の
envision 心に［思い］描く、想像する
notably 特に、とりわけ
type speculation 型推測？
Fast Compilation 高速コンパイル
Stencil ステンシル
Optimization 最適化
Execution Performance 実行性能
Code Generation コード生成
Interpreter インタープリタ
Register Allocation レジスタ割り当て
Stack Offset スタックオフセット
Binary Patching バイナリパッチ適用
Compilation Latency コンパイル遅延
Execution Time 実行時間
Baseline Compiler ベースラインコンパイラ
TurboFan （Google Chromeの）TurboFanコンパイラ
Liftoff （Google Chromeの）Liftoffコンパイラ
Code Variant Library コードバリアントライブラリ
Memory Footprint メモリフットプリント
プログラムが実行中に使用または参照するメインメモリの合計量
Supernode スーパーノード
Continuation-Passing Style (CPS) 継続渡しスタイル（CPS）
Function Call Overhead 関数呼び出しオーバーヘッド
Spilled Temporary スピルされた一時変数
LLVM Optimization Levels LLVM最適化レベル
Stack Frame Layout スタックフレームレイアウト
External Function Call 外部関数呼び出し
Exception Propagation 例外伝播
Stencil Generator ステンシル生成器
Binary Stencil バイナリステンシル
Function Prototype 関数プロトタイプ
Loop Unrolling ループ展開
Mem2Reg Optimization Mem2Reg最適化
Performance Benchmark 性能ベンチマーク
intermediate representation 中間表現(IR) parallelism 並列性
static analysis 静的解析
dynamic analysis 動的解析
linearization 直線化？
パレートフロンティア(パレートフロント)とは
多目的最適化問題、パレート解、パレートフロンティアの語彙から理解する
多目的最適化問題という、複数の目的関数について最適化を行う問題がある。
パレート解は、2つの目的関数を同時に最少化(または最大化？)できないような点
パレートフロンティアはパレート解の集合
参考
メモ
関連